#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

// 二叉树结点结构
typedef struct BiTNode
{
    int data;               // 数据域
    struct BiTNode *lchild; // 左孩子指针
    struct BiTNode *rchild; // 右孩子指针
} BiTNode, *BiTree;

// 1. 初始树（创建空树）
void InitTree(BiTree &T)
{
    T = NULL; // 树根指针置空
}

// 2. 销毁树（递归释放所有结点）
void DestroyTree(BiTree &T)
{
    if (T)
    {
        DestroyTree(T->lchild); // 销毁左子树
        DestroyTree(T->rchild); // 销毁右子树
        free(T);                // 释放当前结点
        T = NULL;               // 指针置空
    }
}

// 3. 插入结点（在指定父结点下插入）
bool InsertNode(BiTree &T, int value, BiTree parent, bool isLeft)
{
    // 创建新结点
    BiTNode *newNode = (BiTNode *)malloc(sizeof(BiTNode));
    if (!newNode)
        return false;

    newNode->data = value;
    newNode->lchild = NULL;
    newNode->rchild = NULL;

    // 插入到根结点位置
    if (parent == NULL)
    {
        if (T != NULL)
        {
            free(newNode); // 根结点已存在
            return false;
        }
        T = newNode; // 设置新根结点
        return true;
    }

    // 插入到左子树位置
    if (isLeft)
    {
        if (parent->lchild != NULL)
        {
            free(newNode); // 左孩子已存在
            return false;
        }
        parent->lchild = newNode;
    }
    // 插入到右子树位置
    else
    {
        if (parent->rchild != NULL)
        {
            free(newNode); // 右孩子已存在
            return false;
        }
        parent->rchild = newNode;
    }
    return true;
}

// 4. 删除结点
bool DeleteNode(BiTree &T, int value)
{
    if (T == NULL)
        return false; // 空树

    // 删除根结点
    if (T->data == value)
    {
        DestroyTree(T); // 销毁整棵树
        return true;
    }

    // 递归查找目标结点
    if (DeleteNode(T->lchild, value))
        return true;
    if (DeleteNode(T->rchild, value))
        return true;

    return false; // 未找到目标结点
}

// 前序遍历辅助函数
void PreOrder(BiTree T)
{
    if (T)
    {
        printf("%d ", T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

// 中序遍历辅助函数
void InOrder(BiTree T)
{
    if (T)
    {
        InOrder(T->lchild);
        printf("%d ", T->data);
        InOrder(T->rchild);
    }
}

// 后序遍历辅助函数
void PostOrder(BiTree T)
{
    if (T)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%d ", T->data);
    }
}

// 层序遍历（使用队列）
void LevelOrder(BiTree T)
{
    if (!T)
        return;

    // 创建队列
    BiTree queue[100];
    int front = 0, rear = 0;

    queue[rear++] = T; // 根结点入队

    while (front < rear)
    {
        BiTree node = queue[front++];
        printf("%d ", node->data);

        if (node->lchild)
            queue[rear++] = node->lchild;
        if (node->rchild)
            queue[rear++] = node->rchild;
    }
}

// 5. 遍历树（选择不同遍历方式）
void Traversal(BiTree T, const char *order)
{
    if (strcmp(order, "preorder") == 0)
        PreOrder(T);
    else if (strcmp(order, "inorder") == 0)
        InOrder(T);
    else if (strcmp(order, "postorder") == 0)
        PostOrder(T);
    else if (strcmp(order, "levelorder") == 0)
        LevelOrder(T);
    printf("\n");
}

// 6. 查找结点（返回结点指针）
BiTree Search(BiTree T, int value)
{
    if (T == NULL)
        return NULL;

    if (T->data == value)
        return T;

    BiTree left = Search(T->lchild, value);
    if (left)
        return left;

    return Search(T->rchild, value);
}

// 7. 判空树
bool TreeEmpty(BiTree T)
{
    return (T == NULL);
}

// 8. 获取树深度（递归计算）
int TreeDepth(BiTree T)
{
    if (T == NULL)
        return 0;

    int leftDepth = TreeDepth(T->lchild);
    int rightDepth = TreeDepth(T->rchild);

    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

int main()
{
    BiTree T;
    InitTree(T);

    // 插入根结点
    InsertNode(T, 1, NULL, true);
    printf("After inserting root node 1, is tree empty? %s\n", TreeEmpty(T) ? "Yes" : "No");

    // 插入其他结点
    InsertNode(T, 2, T, true);            // 1的左孩子
    InsertNode(T, 3, T, false);           // 1的右孩子
    InsertNode(T, 4, Search(T, 2), true); // 2的左孩子

    // 获取深度
    printf("Tree depth: %d\n", TreeDepth(T));

    // 遍历测试
    printf("Preorder traversal: ");
    Traversal(T, "preorder");

    printf("Inorder traversal: ");
    Traversal(T, "inorder");

    printf("Postorder traversal: ");
    Traversal(T, "postorder");

    printf("Levelorder traversal: ");
    Traversal(T, "levelorder");

    // 删除结点测试
    DeleteNode(T, 2);
    printf("After deleting node with value 2:\n");
    printf("Levelorder traversal: ");
    Traversal(T, "levelorder");

    printf("Tree depth: %d\n", TreeDepth(T));

    DestroyTree(T);
    return 0;
}
